package bm4;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/7/20 0:11
 * BM4.合并两个排序链表
 * https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=295&tqId=23267&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // 构造哑巴节点, 最终返回的结果为 muteNode.next
        ListNode muteNode = new ListNode(-1);
        // 构造辅助指针
        ListNode curA = pHead1;
        ListNode curB = pHead2;
        ListNode cur = muteNode;
        // 合并过程
        while (curA != null && curB != null) {
            if (curA.val <= curB.val) {
                cur.next = curA;
                curA = curA.next;
            } else {
                cur.next = curB;
                curB = curB.next;
            }
            cur = cur.next;
        }
        // 处理剩余的部分
        if (curA != null) {
            cur.next = curA;
        }
        if (curB != null) {
            cur.next = curB;
        }
        return muteNode.next;
    }

    private static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
}
